package com.company.剑指offer每日刷题.普通版;

/**
 * 剑指 Offer 26. 树的子结构
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 *
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 *
 * 例如:
 * 给定的树 A:
 *
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 * 给定的树 B：
 *
 *    4
 *   /
 *  1
 * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
 *
 * 示例 1：
 *
 * 输入：A = [1,2,3], B = [3,1]
 * 输出：false
 * 示例 2：
 *
 * 输入：A = [3,4,5,1,2], B = [4,1]
 * 输出：true
 * 限制：
 *
 * 0 <= 节点个数 <= 10000
 * */
public class IsSubStructure {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    /**
     * 方法：递归遍历
     * 思路：递归遍历每个A节点，将所有A节点为根节点的子树判断一次
     * */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){
            return false;
        }
        return recur(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
    public boolean recur(TreeNode A,TreeNode B){
        if(B == null) return true;
        if(A == null) return false;     //等价于 　if(A == null && B!=null) return false;
        if(A.val == B.val)
            return recur(A.left,B.left) && recur(A.right,B.right);
        else return false;
    }
}
